Multicast communication that distributes moving image and sound to many particular users through a computer network is drawing attention. This communication method distributes information from a starting point to selected one or more ending points by copying the information at branches. If the information is distributed using a unicast communication method that communicates between the starting point and the many particular ending points on a 1-to-1 basis, as many copies of the information as the number of the particular many ending points needs to be prepared at the starting point. The use of the multicast communication reduces network traffic. According to the multicast communication, the many particular ending points are managed by a unit called a multicast group, and a transfer route is set for each multicast group. The transfer route is set in a manner in which the starting point and all ending points in the multicast group are connected. If a user desires to obtain the information distributed to a particular multicast group, the user can obtain the information by joining the multicast group. As a result, the transfer route may change in accordance with the users who participate in the multicast group.
Video conference, on-line games, motion pictures, and television are examples of applications to which the multicast communication is applicable. In the case of the video conference, delay in data transfer is an important performance. It is known that, in ordinary conversations, if voice reaches counterpart only with 100 ms delay or less, participants feel that the ordinary conversation is natural. Consequently, if the above applications are to be provided, the delay in data transfer needs to be constrained below a particular value in order to provide customers satisfactory service. There is a method of selecting a transfer route from the starting point to the ending point, wherein the transfer route satisfies a delay condition required by an application.
When a route for the multicast communication is computed, the cost of the entire route needs to be reduced in order to reduce task of network administrators and the user fee that the users of the route need to pay. Consequently, when a service such as video conference is provided, an algorithm that satisfies the delay condition and, at the same time, reduces the cost of the entire route are desired. Such algorithms for selecting a route are called “delay constrained multicast algorithms”. Recently, the realization of delay constrained multicast algorithms that can provide the delay sensitive applications is drawing attention (see document No. 1 and No. 2 listed below, for example).
One of the methods currently proposed is advantageous in reducing the cost of the entire route by computing a low cost route that satisfies the delay condition. This method includes the following steps:
(1) The shortest routes connecting the starting point and the respective ending points are computed.
(2) The highest cost route that connects two of the same kind, or two different kinds, of the starting point, the ending points, and branching points, and that include none of the starting point, the ending points, and the branching points in the middle are selected and removed.
(3) As a result of removal, the selected route is divided in two route trees T1 and T2, where T1 is a partial route tree including the starting point, and T2 is a partial route tree other than T1.
(4) Route of which end points are included in the two route trees and in which the delays incurred between the starting point and the ending point satisfy a prescribed condition are computed as complementary routes for the removed route. One with the least cost is added to the route trees.
(5) One with the second highest cost of the routes selected in (2) is searched.
(6) The above steps (2)-(5) are repeated until the complementary routes for all routes are searched.
If this technique is applied to a service such as video conferencing, a transfer route that realizes a transfer delay or less can be computed (see document No. 2, for example).
The background art described above is described in the following documents:
(Document No. 1) V. Kompella et al., “Multicast routing for multimedia communication,” IEEE/ACM Transactions on Networking, Volume: 1 Issue: 3, pp. 286-292, June 1993, and
(Document No. 2) Q. Zhu et al., “A source-based algorithm for delay-constrained minimum-cost multicasting,” proc. In IEEE INFOCOM '95, vol. 1, pp. 377-385, 1995.
However, there exists the following problems of the above technique in which the cost of the entire route is reduced by computing low cost routes that satisfy the delay condition. According to a report, the computation takes a long time.
Additionally, the above technique is based on an assumption that a link causes the same delay regardless of a direction, upstream or downstream. However, delay caused by a link in an actual network depends on the direction. To solve these problems, the related art may be extended by including the following steps.
(1) When a complementary route is added, a route from the ending point (existing in the partial tree T2) of the complementary route to an ending point existing in T2 is re-computed.
(2) Delay caused between the starting point and the ending point is computed based on the above re-computation, and a determination is made of whether the delay satisfies the delay condition. If the delay does not satisfy the delay condition, a route of the next least cost is selected, and the above step (1) is repeated.
There may be many cases in which the ending point that does not satisfy the delay condition before the extension is made does not satisfy the delay condition even after the extension is made. Since the re-computation of routes may be necessary to cope with such a situation, the computation may take a longer time.
The routes need to be set in a short time in order to provide the service quickly. However, the above technique takes a long time for the computation of routes, and consequently, may delay the beginning of the service.
On the other hand, MPLS (Multi Protocol Label Switching) can be used that sets multicast transfer routes based on the setting of routes computed by the above multicast communication route setting technique. For example, a technique is proposed for label switching transfer in which label switching routes of point-to-multipoint are set (see document No. 3, for example).
Another technique is shown in FIG. 23 that makes multicast transfer possible in a VPN using the MPLS. In the case of the technique shown in FIG. 23, PIM (Protocol Independent Multicast) instance in a VPN site and PIM instance in the provider network are distinguished. A PE router is provided with a VRF table for handling the PIM instance of each accommodated VPN site. The provider network is provided with common PIM instance (see document No. 4, for example).
The above background art is described in the following documents.
(document No. 3)
Extended RSVP-TE for Multicast LSP Tunnels (available at the IETF website as draft-yasukawa-mpls-rsvp-multicast-01.txt)
(document No. 4)
MPLS/BGP VPNs (available at the IETF website as internet-draft/draft-rosen-vpn-mcast -04.txt)
The technique that sets the multicast distribution routes using the conventional MPLS can set the label switching routes of point-to-multipoint using MPLS for the label switching transfer. However, the label switching route is a label switching route of a single layered point-to-multipoint. As a result, all input traffic label-switched by the label switching route is transferred to the same destination. That is, it is label-transferred to all reef nodes constituting the label switching route.
FIG. 24 shows the problem of the above technique. The first layer multicast LSP (Label Switched Path) is set from a provider edge router PE#1 to provider edge routers PE#2, 3, and 4. The traffic of customer edge routers CE#A1, B1, and C1 accommodated in the provider edge router PE#1 is transferred in accordance with the same topology regardless of the states of respective groups under the provider edge routers PE#2, 3, and 4. This means that the multicast traffic is transferred to unneeded points, which is not preferable. For example, there is no C1 group receiver under the provider edge router PE#2, but the traffic for the C1 group is distributed. This causes excessive use of the network resource.
As described above, the label switching using the above technique realizes the label transfer of the same transfer topology as point-to-multipoint. As a result, when traffic is intended to be multicast-distributed to a subgroup, or a subset of a leaf node group that shares the label switch LSP of the set point-to-multipoint, and constitutes the label switch LSP, the traffic is multicast-label distributed to leaf nodes other than those constituting the subgroup. The traffic cannot be partially multicast-transferred.
Furthermore, in order to realize multicast transfer on the VPN using the MPLS, PIM-SM multicast routing protocol is required to be installed in the provider network. In the case of VPN multicast technique shown in FIG. 23, the PIM instance in the VPN site and the PIM instance in the provider network are distinguished. The PE router is provided with VRF table for handling the PIM instances of respective accommodated VPN sites.
At the provider network side, PIM instance common for the provider network is provided. Multicast distribution routes are formed between the PE routers for each VPN site using a rendezvous point. Multicast routes for VPN#A and VPN#B are established in the example shown in FIG. 23. As widely known, PIM-SM (Protocol Independent Multicast Sparse Mode) is IP multicast routing protocol. The PIM-SM requires a rendezvous point for realizing multicast distribution, and since the rendezvous point becomes a single trouble point, the PIM-SM is not reliable. Additionally, in the case of the PIM-SM, although the multicast distribution route is established in the provider network, a path of which QoS (Quality of Service) is secured and a path route depending on traffic cannot be set. Thus, the PIM-SM has problems such that it cannot guarantee QoS of the network and cannot realize traffic engineering.
The PIM-SM, which requires P router (provider router) in the provider network to handle multicast state ((S, G), (*, G)), frequently changes the multicast state on the multicast route in accordance with the receiving state of multicast traffic. Since the PIM-SM requires the high speed P router of the provider core to often change its state, the use of PIM-SM is not practical.
Additionally, the PIM-SM has a problem that, because a multicast route is established for each VPN, the number of multicast connections in the provider network increases. Furthermore, because the traffic distribution pattern in the multicast connection is uncontrollable, if plural multicast traffics exist in the VPN site, unnecessary traffic is delivered to a VPN site without any receiver.